package NewCoder;

public class BM12 {
    //归并排序链表
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head==null || head.next==null) return head;
        ListNode slow=head;
        ListNode fast=head.next;
        //使用快慢指针找到链表中点
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }

        //将链表分成两个部分
        ListNode tmp=slow.next;
        slow.next=null;

        //递归左右两边进行排序
        ListNode left=sortInList(head);
        ListNode right=sortInList(tmp);

        //创建新链表
        ListNode h=new ListNode(0);
        ListNode node=h;

        //合并 left right 两个链表
        while(left!=null && right!=null){
            if(left.val<right.val){
                node.next=left;
                left=left.next;
            }else{
                node.next=right;
                right=right.next;
            }
            node=node.next;
        }
        node.next=left!=null?left:right;
        return h.next;
    }
}
